{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Minimum Time to Finish All Jobs II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成所有工作的最短时间 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <b>下标从 0 开始&nbsp;</b>的整数数组 <code>jobs</code> 和&nbsp;<strong>相等&nbsp;</strong>长度的 <code>workers</code> ，其中&nbsp;<code>jobs[i]</code>是完成第 <code>i</code> 个工作所需的时间，<code>workers[j]</code>&nbsp;是第 <code>j</code> 个工人每天可以工作的时间。</p>\n",
    "\n",
    "<p>每项工作都应该 <strong>正好</strong> 分配给一个工人，这样每个工人就&nbsp;<strong>只能&nbsp;</strong>完成一项工作。</p>\n",
    "\n",
    "<p>返回<em>分配后完成所有作业所需的最少天数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> jobs = [5,2,4], workers = [1,7,5]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "- 把第 2 个工人分配到第 0 个工作。他们花了 1 天时间完成这项工作。\n",
    "- 把第 0 个工人分配到第 1 个工作。他们花了 2 天时间完成这项工作。\n",
    "- 把第 1 个工人分配到第 2 个工作。他们花了 1 天时间完成这项工作。\n",
    "所有工作完成需要 2 天，因此返回 2。\n",
    "可以证明 2 天是最少需要的天数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> jobs = [3,18,15,9], workers = [6,5,1,3]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "- 把第 2 个工人分配到第 0 个工作。他花了 3 天时间完成这项工作。\n",
    "- 把第 0 个工人分配到第 1 个工作。他花了 3 天时间完成这项工作。\n",
    "- 把第 1 个工人分配到第 2 个工作。他花了 3 天时间完成这项工作。\n",
    "- 把第 3 个工人分配到第 3 个工作。他花了 3 天时间完成这项工作。\n",
    "完成所有工作需要 3 天，因此返回 3。\n",
    "可以证明，3 天是最少需要的天数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == jobs.length == workers.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= jobs[i], workers[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-minimum-time-to-finish-all-jobs-ii](https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-minimum-time-to-finish-all-jobs-ii](https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,4]\\n[1,7,5]', '[3,18,15,9]\\n[6,5,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort(reverse=True)\n",
    "        workers.sort(reverse=True)\n",
    "        ans=0\n",
    "        for i,k in enumerate(jobs):\n",
    "            ans=max(ans,(k+workers[i]-1)//workers[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        return max(ceil(x / y) for x, y in zip(jobs, workers))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        ans = 0\n",
    "        n = len(jobs)\n",
    "        for i in range(n):\n",
    "            t = jobs[i] // workers[i]\n",
    "            if jobs[i] % workers[i]:\n",
    "                t += 1\n",
    "            ans = max(ans,t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        ans = 0\n",
    "        n = len(jobs)\n",
    "        for i in range(n):\n",
    "            t = jobs[i] // workers[i]\n",
    "            if jobs[i] % workers[i]:\n",
    "                t += 1\n",
    "            ans = max(ans,t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 贪心\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        workers.sort()\n",
    "        jobs.sort()\n",
    "        ans = 1\n",
    "        for i, job in enumerate(jobs):\n",
    "            ans = max(ans, math.ceil(job / workers[i]))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        ans = 0\n",
    "        n = len(jobs)\n",
    "        for i in range(n):\n",
    "            t = jobs[i] // workers[i]\n",
    "            if jobs[i] % workers[i]:\n",
    "                t += 1\n",
    "            ans = max(ans,t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        res = 0\n",
    "        for i in range(len(jobs)):\n",
    "            res = max(res, math.ceil(jobs[i] / workers[i]))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        return max(ceil(x / y) for x, y in zip(sorted(jobs), sorted(workers)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        res=0\n",
    "        for i in range(len(workers)):\n",
    "            if jobs[i]%workers[i]==0:\n",
    "                res=max(res,jobs[i]//workers[i])\n",
    "            else:\n",
    "                res=max(res,jobs[i]//workers[i]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:\n",
    "        jobs.sort()\n",
    "        workers.sort()\n",
    "        return max(ceil(x / y) for x, y in zip(jobs, workers))\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
